/*
Date:20210430 13:21PM
key:1.我的首选是递归法，类似反转链表的操作。
    一开始先递归到尽头，然后返回尽头指针。
    比较返回的下一个与当前个val，匹配则继续返回头，不匹配则交换，对下一个继续递归，结束后同样返回头。
    以上这种做法类似冒泡，复杂度要n^2，但只需要常熟空间。
    2.归并排序，先分后治疗，分是通过快慢指针找到中点的。
 */
class Solution {
public:
void swap(int&a,int&b)
{

    if(a!=b)
    {
        a=a^b;
        b=a^b;
        a=a^b;
    }
}
//快慢指针找中间节点，切完要断尾。
ListNode* findmi(ListNode* head)
{
    ListNode* f=head;
    ListNode* s=head;
    int i=2;
    while(f!=nullptr)
    {
        if(i&1){s=s->next;}
        i++;
        f=f->next;
    }
    //这里严格来说是切多了一个，因为只能切s-next.
    ListNode*m=s->next;
    s->next=nullptr;
    return m;
}
//合并两个有序链表
ListNode* merge(ListNode* l,ListNode* r)
{
    //切小的当头
    ListNode*head;
    if(l->val>r->val)
    {
        head=r;
        r=r->next;
    }
    else
    {
        head=l;
        l=l->next;
    }
    //保留头
    ListNode*head1=head;
    while(l!=nullptr&&r!=nullptr)
    {
        if(l->val>r->val)
        {
            
            head->next=r;
            r=r->next;
            head=head->next;
            //head->next=nullptr;
        }
    else
        {
            head->next=l;
            l=l->next;
            head=head->next;
        }
    }
    while(l!=nullptr)
    {
            head->next=l;
            l=l->next;
            head=head->next;
    }
    while(r!=nullptr)
    {
        head->next=r;
            r=r->next;
            head=head->next;
    }
    return head1;
}
//这一步是划分
ListNode* GuiBing(ListNode* head)
{
    //切到一个的时候不切
    if(head->next==nullptr)
    {
        return head;
    }
    else
    {
        //切到2个的时候判断交换
        if(head->next->next==nullptr)
        {
            if(head->val>head->next->val)
            {
                swap(head->val,head->next->val);
            }
            return head;
        }
        else
        {
            //3个以上就要找到中间指针并切断
            ListNode*m=findmi(head);
            return merge(GuiBing(head),GuiBing(m));
        }
    }
}
ListNode* back(ListNode* head)
{
    if(head->next!=nullptr)
    {
        ListNode*p=back(head->next);
        if(p->val<head->val)
        {
            swap(p->val,head->val);
            back(head->next);
            return head;
        }

        else
        {
            return head;
        }
    }
    else
    {
        return head;
    }
}
    ListNode* sortList(ListNode* head) 
    {
        if(head==nullptr){return nullptr;}
        return GuiBing(head);
    }
};